#include "btree.hpp"

bool PrecedThan(char c1, char c2)
{
    return ('*' == c1 || '/' == c1) &&
           ('+' == c2 || '-' == c2);
}


class BCalcTree : public BTree
{
public:
    void BuildFromInfix(char const* expression)
    {
        stack<BTreeNode*> stkNode;
        stack<char> stkOprt;
        char const* pExpr = expression;
        
        char ch;
        while ('\0' != (ch = *pExpr++))
        {
            if (isalpha(ch))
            {
                BTreeNode* pNode = new BTreeNode;
                pNode->value = ch;
                stkNode.push(pNode);
            }
            else
            {
                char chTop;
                
                switch (ch)
                {
                case '(':
                    stkOprt.push(ch);
                    break;
                case ')':
                    while ('(' != (chTop = stkOprt.top()))
                    {
                        CreateSubTree(stkNode, chTop);
                        stkOprt.pop();
                    }
                    stkOprt.pop();
                    break;
                default:
                    while (!stkOprt.empty())
                    {
                        chTop = stkOprt.top();
                        if ('(' == chTop || PrecedThan(ch, chTop))
                        {
                            break;
                        }
                        else
                        {
                            CreateSubTree(stkNode, chTop);
                            stkOprt.pop();
                        }
                    }
                    stkOprt.push(ch);
                    break;
                }//end of switch
            }//end of if...else
        }//end of while
        
        while (!stkOprt.empty())
        {
            char chTop = stkOprt.top();
            CreateSubTree(stkNode, chTop);
            stkOprt.pop();
        }
        
        root = stkNode.top();
    }
private:
    void CreateSubTree(stack<BTreeNode*>& rStkNode, char ch)
    {
        BTreeNode* pNode = new BTreeNode;
        pNode->value = ch;
        
        pNode->pRight = rStkNode.top();
        rStkNode.pop();
        pNode->pLeft = rStkNode.top();
        rStkNode.pop();
        
        rStkNode.push(pNode);
    }
};

int main(void)
{
    BCalcTree testTree;
	testTree.BuildFromInfix("(a+b)*c-d/e");
	char str[50] = {0};
	testTree.ConvertTo(str);
	cout<< str <<endl;
	
    system("pause");
}
